package lanqiao._02算法训练.page01;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
 * 输入格式
 * 　　一行两个正整数n和m
 * 输出格式
 * 　　一个实数P表示答案，保留4位小数。
 * 样例输入
 * 2 3
 * 样例输出
 * 0.7500
 * 数据规模和约定
 * 1≤n，m≤20
 * @since 2022 - 10 - 28 - 19:37
 */
public class _01印章 {
}
class Main1{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //dp[i][j] i张 收集 j种的概率
        double[][] dp = new double[m + 1][n + 1];
        //每一张 概率都为p
        double p = 1.0 / n;

        dp[0][0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i < j){ //这样找不出来 概率为0
                    dp[i][j] = 0;
                }else if(j == 1){ //表示某一种印章出现了i次
                    /*
                    n种 中任选一种 : i 张 同印章
                    p ^ i * n = p ^ i * 1/ p = p ^ (i - 1)
                     */
                    dp[i][j] = Math.pow(p, i - 1);
                }else{ //包括重复的和不重复的
                    /*
                    选重复： dp[i-1][j] i-1 张 凑够 j种
                    这一张任选j种中的一种 dp[i - 1][j] * p * j
                    不与前面重复： dp[i - 1][j - 1] i - 1 张 凑 j - 1种
                    这一张是 这j - 1 种外的任意一种
                    dp[i - 1][j - 1] * (n - j + 1) * p
                     */
                    dp[i][j] = dp[i - 1][j] * (j * p)
                            + dp[i - 1][j - 1] * ((n - j + 1) * p);
                }
            }
        }
        for(double[] arr : dp){
            System.out.println(Arrays.toString(arr));
        }
        System.out.printf("%.4f", dp[m][n]);
    }
}
